#include <stdio.h>

typedef int Int;

Int Random(Int a, Int b) {
  return a;
}

Int ModularExp(Int a, Int b, Int n) {
  Int d = 1;
  Int tmp = a;
  while (b > 0) {
    if ((b & 1) != 0) d = (d * tmp) % n;
    tmp = (tmp * tmp) % n;
    b >>= 1;
  }
  return d;
}

// n: odd number greater than 2
bool PseudoPrime(Int n) {
  if (ModularExp(2, n - 1, n) != 1) return false;
  return true;
}

// return true is n is composite
bool Witness(Int a, Int n) {
  Int u = n - 1, t = 0;
  while ((u & 1) == 0) {
    ++t;
    u >>= 1;
  }

  Int x = ModularExp(a, u, n);
  for (int i = 0; i < t; ++i) {
    Int xi = (x * x) % n;
    if (xi == 1 && x != 1 && x != n - 1)
      return true;
    x = xi;
  }
  if (x != 1) return true;
  return false;
}

bool MillerRabin(Int n, Int s) {
  for (Int i = 0; i < s; ++i) {
    Int a = Random(1, n - 1);
    if (Witness(a, n)) return false;
  }
  return true;
}

int main(int argc, const char *argv[]) {
  printf("%d\n", ModularExp(7, 560, 561));
  return 0;
}

